#
# @lc app=leetcode.cn id=2246 lang=python3
#
# [2246] 相邻字符不同的最长路径
#

# @lc code=start
class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        # 构造树
        n = len(parent)
        tree = [[] for _ in range(n)]
        # 节点 0 是根节点，所以 parent[0] == -1 。
        for i in range(1, n): #
            tree[parent[i]].append(i)
        ans = 0
        def dfs(x):
            nonlocal ans
            x_len = 0
            for y in tree[x]:
                y_len = dfs(y) + 1
                if s[x] != s[y]: # 相邻字符不同
                    ans = max(x_len+y_len, ans)
                    x_len = max(y_len, x_len)
            return x_len
        dfs(0)
        
        return ans + 1 # 为什么+1?
                
# @lc code=end

